# 柱状图中最大的矩形: https://leetcode-cn.com/problems/largest-rectangle-in-histogram/

# 暴力破解O(n^2)超时
class Solution:
    def largestRectangleArea(self, heights: list) -> int:
        """
            依次枚举宽， 然后高的话就是最小的那个. 还可以枚举高，都是差不多的
        """
        n = len(heights)
        maxArea = 0
        
        for i in range(n):
            minHigh = heights[i]
            for j in range(i, n):
                # 宽
                width = j - i + 1
                # 高
                minHigh = min(minHigh, heights[j])
                # 面积    
                area = minHigh * width
                maxArea = max(area, maxArea)
        
        return maxArea

# 单调栈加双数组记录 左右最近最小值，优化实现
class Solution:
    def largestRectangleArea(self, heights: list) -> int:
        """
            枚举高，也就是以每一个柱子的高，确定它的宽，左右两边都是要大于等于 该高。 
            使用栈优化的话，也就是，寻找该位置，左边第一个小于它的值，右边第一个小于它的值，那么就将问题清晰化了
        """
        n = len(heights)
        left = [-1] * n
        right = [n] * n
        stack = list()
        # 右边第一个小的
        for i in range(n):
            while stack and heights[i] < heights[stack[-1]]:
                right[stack.pop()] = i
            stack.append(i)
        # 左边第一个小的
        for i in range(n-1, -1, -1):
            while stack and heights[i] < heights[stack[-1]]: # 注意这里比较的是heights元素值
                left[stack.pop()] = i
            stack.append(i)

        # 计算最大面积
        maxArea = 0
        for i in range(n):
            width = right[i] - left[i] - 1
            high = heights[i]
            maxArea = max(width * high, maxArea)

        return maxArea


# 官方最优解： 优化上面的两次求 左右最近最小。一次循环解决
class Solution:
    def largestRectangleArea(self, heights: list) -> int:
        n = len(heights)
        left, right = [0] * n, [n] * n

        mono_stack = list()
        for i in range(n):
            while mono_stack and heights[mono_stack[-1]] >= heights[i]:
                right[mono_stack[-1]] = i
                mono_stack.pop()
            left[i] = mono_stack[-1] if mono_stack else -1
            mono_stack.append(i)
        
        ans = max((right[i] - left[i] - 1) * heights[i] for i in range(n)) if n > 0 else 0
        return ans


heights = [2,1,5,6,2,3]

s = Solution()
rst = s.largestRectangleArea(heights)
print(rst)

